/*
 * Chart.java
 *
 * Created on June 27, 2006, 7:02 PM
 *
 */

package galronnlp.pcfg.parser;

import galronnlp.util.SymbolTuple;
import java.util.Hashtable;
import java.util.LinkedList;
import java.util.Enumeration;
import java.util.Iterator;

import galronnlp.util.Grammar;
import galronnlp.util.Tuple;
import galronnlp.util.Symbol;

/**
 * The chart has the following semantics. It is indexed by a tuple consisting of
 * a start position an end position and a category. The result is a storage 
 * element which does one of two things
 *
 *  1) In all-paths mode it unconditionally adds
 *  the probability and the backtrace token to itself
 *
 *  2) In best-path mode it replaces the probability and
 *  the backtrace token if it is better than the best so
 *  far.
 *
 * In both cases the storage elements has two attributes elem.p stores the 
 * probability (best or total) of the element elem.items stores the individual 
 * items
 * There are two modes, an all paths mode and a best path mode. The difference 
 * is localized in the behaviour of the inmost elements of the chart, which are 
 * called All and Best.
 *
 * @author Chris Brew
 * @author Daniel A. Galron
 */
public class Chart {
    
    public static final int ALL  = 0;
    public static final int BEST = 1;
    
    
    private boolean TRACE = false;
    private int EntryType = BEST;
    
    /** 
     * This is the chart datastructure. It is a Hashtable indexed by KeyDouble,
     * which is a 2-tuple of (i, j). The value at each entry is another Hashtable,
     * indexed by Symbol, the left-hand side symbol which spans (i, j), and whose
     * value is a ChartEntry. This ChartEntry could either be an AllChartEntry
     * object or a BestChartEntry object.
     */
    private Hashtable<KeyDouble, Hashtable<Symbol, ChartEntry>> chart = new Hashtable<KeyDouble, Hashtable<Symbol, ChartEntry>>();
    
    /** 
     * Creates a new instance of Chart 
     * @param EntryType can be either ALL or BEST; ALL if one wants to store all
     * the items, BEST if one wants to store only the best item
     * @param trace print debug info
     */
    public Chart(int EntryType, boolean trace) {
        this.TRACE = trace;
        this.EntryType = EntryType;
    }
    public Chart(int EntryType) {
        this.EntryType = EntryType;
    }
    
    /**
     * @return the ChartEntry indexed at [(begin, end)][cat]
     */
    public ChartEntry get(int begin, int end, Symbol cat) {
        return this.chart.get(new KeyDouble(new Integer(begin), new Integer(end))).get(cat);
    }
    
    /**
     * Adds the entry to the chart, at index [(begin, end)][cat]
     * @param begin the start of the span
     * @param end the end of the span
     * @param cat the LHS covering the span
     * @param entry the edge and associated data (i.e. count and probability) to
     * put into the chart
     */
    public void add(int begin, int end, Symbol cat, EntryTriple entry) {
        if(TRACE)
            System.out.println("Adding (" + begin + ", " + end + "): [" + cat + "] " + entry);
        // Create a new KeyDouble to use as the index in the chart
        KeyDouble key = new KeyDouble(new Integer(begin), new Integer(end));
        
        // If there is not already an entry at (begin, end) in the chart, create a new 
        // hashtable
        if(!this.chart.containsKey(key)) {
            this.chart.put(key, new Hashtable<Symbol, ChartEntry>());
        }
        // If the hashtable at (begin, end) does not contain the LHS symbol, then
        if(!this.chart.get(key).containsKey(cat)) {
            // if we only want to store the best (i.e. highest-probability) item,
            // create a new BestChartEntry and put it in the hashtable indexed
            // by the LHS
            if(this.EntryType == BEST) {
                this.chart.get(key).put(cat, new BestChartEntry());
            // Otherwise, if we want to store all items, create a new AllChartEntry
            // and put it in the hashtable indexed by the LHS
            } else {
                this.chart.get(key).put(cat, new AllChartEntry());
            }                
        }
        // add the new entry to the chart
        this.chart.get(key).get(cat).add(entry);
    }
    
    /**
     * @return a LinkedList containing all Unary rule expansions where the RHS of
     * the new Unary edges is the LHS stored at chart entry (begin, end)
     */
    public LinkedList<Tuple> expandUnary(Grammar gram, int begin, int end) {
        // Get the hashtable stored at index (begin, end)
        Hashtable<Symbol, ChartEntry> dtrs = chart.get(new KeyDouble(new Integer(begin), new Integer(end)));
        // If there is nothing there, (that is, the chart does not contain index (begin, end))
        // return an empty list of Tuples
        if(dtrs == null) {
            return new LinkedList<Tuple>();
        }
        // Create the return list
        LinkedList<Tuple> xs = new LinkedList<Tuple>();
        // For each LHS Symbol in span (begin, end) do:
        for(Enumeration<Symbol> e = dtrs.keys(); e.hasMoreElements(); ) {
            // Get the next LHS symbol, the probability of the edge corresponding
            // to the symbol, and the count of the edge corresponding to the symbol
            Symbol dtr = e.nextElement();
            double dtrp = dtrs.get(dtr).probability();
            int count   = dtrs.get(dtr).count();
            // Retrieve all unary rules where the RHS of the rule is the LHS of
            // the span
            LinkedList<Tuple> unaryRules = gram.unaryRules.get(dtr);
            // If no rules are found, ...
            if(unaryRules == null) {
                return xs;
            }
            // for each rule found with RHS matching the LHS of the span, construct
            // a new tuple and add it to the end of the return object.
            for(Iterator<Tuple> i = unaryRules.iterator(); i.hasNext(); ) {
                Tuple tup = i.next();
                Symbol LHS = (Symbol)tup.get(0);
                double rulep = ((Double)tup.get(1)).doubleValue();
                Tuple returnTuple = new Tuple(4);
                returnTuple.put(0, LHS); returnTuple.put(1, dtr); returnTuple.put(2, new Double(dtrp * rulep)); returnTuple.put(3, new Integer(count));
                xs.addLast(returnTuple);
            }
        }
        return xs;
    }

    /**
     * @return a LinkedList containing all Binary rule expansions where the RHS of
     * the new Binary edges is the LHS stored at chart entry (begin, mid) and the
     * LHS stored at chart entry (mid, end)
     */    
    public LinkedList<Tuple> expandBinary(Grammar gram, int begin, int mid, int end) {
        // Get the hashtable stored at index (begin, mid)
        Hashtable<Symbol, ChartEntry> ldtrs = chart.get(new KeyDouble(new Integer(begin), new Integer(mid)));
        // If there is nothing there, (that is, the chart does not contain index (begin, mid))
        // return an empty list of Tuples
        if(ldtrs == null) {
            return new LinkedList<Tuple>();
        }
        // Get the hashtable stored at index (mid, end)
        Hashtable<Symbol, ChartEntry> rdtrs = chart.get(new KeyDouble(new Integer(mid), new Integer(end)));
        // If there is nothing there, (that is, the chart does not contain index (begin, mid))
        // return an empty list of Tuples
        if(rdtrs == null) {
            return new LinkedList<Tuple>();
        }
        // Create the return LinkedList
        LinkedList<Tuple> xs = new LinkedList<Tuple>();
        // For each Symbol stored at (begin, mid)
        for(Enumeration<Symbol> le = ldtrs.keys(); le.hasMoreElements(); ) {
            // get the symbol
            Symbol ldtr = le.nextElement();
            // For each Symbol stored at (mid, end)
            for(Enumeration<Symbol> re = rdtrs.keys(); re.hasMoreElements(); ) {
                // get the symbol
                Symbol rdtr = re.nextElement();
                // get the probabilities of the left side and right side productions
                double leftp  = ldtrs.get(ldtr).probability();
                double rightp = rdtrs.get(rdtr).probability();
                // get the counts of the left side and right side productions
                int count     = ldtrs.get(ldtr).count() * rdtrs.get(rdtr).count();
                // create a new Tuple of symbols containing the left RHS symbols and the right
                // RHS symbols
                SymbolTuple doubleTuple = new SymbolTuple(ldtr, rdtr);
                // get all binary rules whose RHS is the left symbol followed by the right
                // symbols
                LinkedList<Tuple> binaryRules = gram.binaryRules.get(doubleTuple);
                // If there are some rules found with the proper RHS
                if(binaryRules != null) {
                    // Iterate throug hall the binary rules, and add the resulting tuple
                    // to the return object
                    for(Iterator<Tuple> i = binaryRules.iterator(); i.hasNext(); ) {
                        Tuple tup = i.next();
                        Symbol LHS = (Symbol)tup.get(0);
                        double rulep = ((Double)tup.get(1)).doubleValue();
                        Tuple returnTuple = new Tuple(5);
                        returnTuple.put(0, LHS); returnTuple.put(1, ldtr); returnTuple.put(2, rdtr); returnTuple.put(3, new Double(leftp * rightp * rulep)); returnTuple.put(4, count);
                        xs.addLast(returnTuple);
                    }
                }
            }
        }
        return xs;
    }
    
    public int size() {
        return chart.size();
    }
    
    public String toString() {
        String ret = "";
        for(Enumeration<KeyDouble> e1 = chart.keys(); e1.hasMoreElements(); ) {
            KeyDouble key = e1.nextElement();
            ret += "[" + key + ": (";
            for(Enumeration<Symbol> e2 = chart.get(key).keys(); e2.hasMoreElements(); ) {
                Symbol LHS = e2.nextElement();
                ret += LHS + ": " + chart.get(key).get(LHS) + " ";
            }
            ret += ")]\n";
        }
        return ret;
    }

    /**
     * @return true if the chart contains the StartSymbol at entry (0, sentence.length())
     */
    public boolean hasFinalEntry(int begin, int end, Symbol symbol) {
        if(chart.containsKey(new KeyDouble(new Integer(begin), new Integer(end)))) {
            return chart.get(new KeyDouble(new Integer(begin), new Integer(end))).containsKey(symbol);
        } else {
            return false;
        }
    }
}
